L2-023 图着色问题

题目 L2-023 图着色问题

思路分析

无向图 用邻接矩阵存

要求判断联通的两个点颜色不同

代码实现

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
using ll = long long;
using ull = unsigned long long;
using PII = pair<int,int>;
using Pll = pair<ll,ll>;
int dx[4]= {-1,0,1,0},dy[4]= {0,1,0,-1};
const int inf = 0x3f3f3f3f;
priority_queue<int> pq;
multiset<int> s;

vector<vector<int>> g;
bool check(int a,int b) {
	cout<<"check: "<<a<<" "<<b<<endl;
	if(g[a][b]==1 && g[b][a]==1) {
		return true;
	}
	return false;
}

signed main() {
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int v,e,k;
	cin>>v>>e>>k;//v个点 e条边 k种颜色
	g.resize(v+1,vector<int>(v+1,0));
	while(e--) {
		int a,b;
		cin>>a>>b;
		g[a][b] = g[b][a] = 1;
	}
//	for(int i=1; i<=v; i++) {
//		for(int j=1; j<=v; j++) {
//			cout<<g[i][j]<<" ";
//		}
//		cout<<endl;
//	}
	int n;cin>>n;
	while(n--) {
		vector<int> colors(v+1);
		unordered_set<int> colorSet;
		for(int i=1; i<=v; i++) {
			cin>>colors[i];
			colorSet.insert(colors[i]);
		}
		if(colorSet.size()!=k) {
			cout<<"No"<<endl;
			continue;
		}

		bool vaild=true;
		for(int i=1;i<=v;i++){
			for(int j=i+1;j<=v;j++){
				if(g[i][j]==1 && colors[i]==colors[j]){
					vaild=false;
					break;
				}
			}
			if(!vaild)	break;
		}
		cout<<(vaild?"Yes":"No")<<endl;
	}

	return 0;
}

同类题型

视频讲解

⬅️ L2-022 重排链表 🏠 00-天梯赛 ➡️ L2-024 部落